package th.retrofit.lib;

import java.util.StringJoiner;

/**
 * 给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。
 */
public class Solution130 {

    public void solve(char[][] board) {
        int rLen = board.length;
        int cLen = board[0].length;
        for (int i = 0; i < cLen; i++) {
            if (board[0][i] == 'O') {
                dfs(board, 0, i);
            }
            if (rLen > 1 && board[rLen - 1][i] == 'O') {
                dfs(board, rLen - 1, i);
            }
        }
        for (int i = 1; i < rLen - 1; i++) {
            if (board[i][0] == 'O') {
                dfs(board, i, 0);
            }
            if (cLen > 1 && board[i][cLen - 1] == 'O') {
                dfs(board, i, cLen - 1);
            }
        }
        for (int i = 0; i < rLen; i++) {
            for (int j = 0; j < cLen; j++) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
                if (board[i][j] == '0') {
                    board[i][j] = 'O';
                }
            }
        }
    }

    private void dfs(char[][] board, int i, int j) {
        if ((i < 0 || i >= board.length) || (j < 0 || j >= board[0].length) || board[i][j] != 'O') return;
        board[i][j] = '0';
        dfs(board, i, j - 1);
        dfs(board, i, j + 1);
        dfs(board, i - 1, j);
        dfs(board, i + 1, j);
    }

    public static void main(String[] args) {
        char[][] board = new char[][]{{'X','X','X','X'},{'X','O','O','X'},{'X','X','O','X'},{'X','O','X','X'}};
        new Solution130().solve(board);
        for (int i = 0; i < board.length; i++) {
            StringJoiner joiner = new StringJoiner(",", "", "");
            for (int j = 0; j < board[0].length; j++) {
                joiner.add(board[i][j] + "");
            }
            System.out.println(joiner.toString());
        }
    }

}
